package com.mdnote.practice.plus_search.prune;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/26 0026
 * @description
 */
public class LeetCode22 {

    public static void main(String[] args) {
        LeetCode22 leetCode22 = new LeetCode22();
        List<String> strings = leetCode22.generateParenthesis(3);
        System.out.println(strings);
    }

    public List<String> generateParenthesis(int n) {

        List<String> list = new ArrayList<String>();

        _generate(0, n, 0, 0, "", list);

        return list;
    }

    public void _generate(int level, int max_level, int left, int right, String res, List<String> resList) {

        // Terminator
        if (level == (max_level * 2)) {
            resList.add(res);
            return;
        }

        // Process current logic
        if (left < max_level) {
            _generate(level + 1,max_level, left + 1, right, res + "(", resList);
        }
        if (right < left) {
            _generate(level + 1, max_level, left, right + 1, res + ")", resList);
        }

    }
}
